package 纯字符串;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class No264丑数II {

    /**
     * 编写一个程序，找出第 n 个丑数。
     * 丑数就是质因数只包含 2, 3, 5 的正整数。
     *
     * 示例:
     * 输入: n = 10
     * 输出: 12
     * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
     * 说明:  
     * 1 是丑数。
     * n 不超过1690。
     */

    //堆版,容易理解
    public int nthUglyNumber(int n) {

        PriorityQueue<Long> minHeap=new PriorityQueue<>();
//        Set<Long> set=new HashSet<>();
//        set.add(1L);
        minHeap.add(1L);
        Long minNum=-1L;//注意要为Long
        int[] arr={2,3,5};

        for (int i = 0; i < n; i++) {

            minNum = minHeap.poll();

            //不用while,用set也行
            while (!minHeap.isEmpty()&& minHeap.peek().equals(minNum)){
                minHeap.poll();
            }

            for (int i1 : arr) {
                long newNum=minNum*i1;
                //这里用set也可以
                minHeap.add(newNum);
            }

        }

        return (int)(long)minNum;
    }

    //动态规划版,比较难理解
    public int nthUglyNumber2(int n) {

        if(n==1){
            return 1;
        }

        //不可复用No263的题目,太慢了
        //可知丑数都是由 2,3,5 因数,那么我们只管乘就行了
        //丑数*丑数=丑数

        int[] dp=new int[n];
        dp[0]=1;

        int i2=0,i3=0,i5=0;

        for (int i = 1; i < n; i++) {

            int n2 = dp[i2] * 2, n3 = dp[i3] * 3, n5 = dp[i5] * 5;
            int minNum=Math.min(Math.min(n2, n3), n5);
            //多个if,同时过滤相等丑数的情况
            if(minNum==n2){
                i2++;
            }
            if(minNum==n3){
                i3++;
            }
            if(minNum==n5){
                i5++;
            }
            dp[i]=minNum;
        }

        return dp[n-1];

    }

    public static void main(String[] args) {
        No264丑数II n=new No264丑数II();
        int result = n.nthUglyNumber(200);
        System.out.println(result);
        System.out.println(n.nthUglyNumber2(200));
    }

}
